package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}18:07
 */
public class LeetCode343 {
    public int integerBreak(int n) {
        int[] memo = new int[n + 1];
//
//        return breakInteger(n,memo);
        return breakInteger(n);
    }

    //递归做法 + 记忆集的做法(自顶向下)
    public int breakInteger(int n,int[] memo){
        if (n == 1){
            return 1;
        }

        if (memo[n] != 0){
            return memo[n];
        }
        int res = -1;
        for (int i = 1; i <= n - 1; i++){
             res = Math.max(res,Math.max(i * (n - i),i * breakInteger(n - i,memo)));
        }
        memo[n] = res;
        return res;
    }


    //动态规划（自底向上）
    public int breakInteger(int n){
        if (n < 2){
            return 1;
        }
        int[] memo = new int[n + 1];
        memo[1] = 1;
        for (int i = 2; i <= n; i++){
            // 求解memo[i]
            for (int j = 1; j <= i - 1; j++){
                //这里比较的三个参数：memo[i]当前的结果；j*(i - j)直接把数分为j和i-j的结果；
                //j * memo[i - j] j * memo(i-j)中的结果-》当数位i-j时的分解的结果，因为此时i-j一定小于i所以一定是有结果的
                memo[i] = Math.max(memo[i],Math.max(j * (i - j),j * memo[i - j]));
            }
        }
        return memo[n];
    }
    public static void main(String[] args) {

        System.out.println(new LeetCode343().integerBreak(3));
    }

}
